# -*- coding: utf-8 -*-
"""
Created on Fri Oct 16 11:09:59 2020

@author: John
"""
import pandas as pd
import numpy as np
import os

# =============================================================================
# 

# =============================================================================

# =============================================================================
# 历史上有10/5/0人以上走过这条路线，就直接推荐（或者按照走过的人数和距离优化结果加权推荐）
# 如果多个提货/卸货城市，按丁博说的，跨省次数尽量少（简单把一个省抽象成一个结点，边的权重是省会城市之间距离（公里），不相邻的省边的权重无限大
# 跨省距离尽量短，Floyd算法 实现
# 没人走过，直接图论方法，或者调地图API解决
# 多个卸货地在不同省，必须经过某个点的最短路规划由明天解决
# =============================================================================

# =============================================================================
# 数据初始化
# =============================================================================
provinces = {'新疆':0,'甘肃':1,'内蒙古':2,'黑龙江':3,'吉林':4,'辽宁':5,'河北':6,\
             '北京':7,'天津':8,'山西':9,'陕西':10,'宁夏':11,'青海':12,'河南':13,\
             '山东':14,'西藏':15,'四川':16,'重庆':17,'湖北':18,'安徽':19,'江苏':20,\
            '贵州':21,'湖南':22,'江西':23,'浙江':24,'云南':25,'广西':26,'广东':27,\
                '福建':28,'海南':29,'香港':30,'澳门':31,'台湾':32,'上海':33}
    
# 由省在权值矩阵中的索引找对应的名称
def findProvinceName(index):
    if index <0 or index >33:
        return ''
    for k,v in provinces.items():
        if v == index:
            return k

linjie = np.array([[0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,1] + [0] * 18, #0
                   [1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,1] + [0]*17,#1
                   [0,1,0,1,1,1,1,0,0,1,1,1] + [0]*22,#2
                   [0,0,1,0,1]+[0]*29,#3
                   [0,0,1,1,0,1]+[0]*28,#4
                   [0,0,1,0,1,0,1]+[0]*27,#5
                   [0,0,1,0,0,1,0,1,1,1,0,0,0,1,1]+[0]*19,#6
                   [0]*6+[1,0,1]+[0]*25,#7
                   [0]*6+[1,1,0]+[0]*25,#8
                   [0,0,1,0,0,0,1,0,0,0,1,0,0,1]+[0]*20,#9
                   [0,1,1,0,0,0,0,0,0,1,0,1,0,1,0,0,1,1,1]+[0]*15,#10
                   [0,1,1,0,0,0,0,0,0,0,1]+[0]*23,#11
                   [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1]+[0]*17,#12,
                   [0]*6+[1,0,0,1,1,0,0,0,1,0,0,0,1,1]+[0]*14,#13
                   [0]*6+[1,0,0,0,0,0,0,1,0,0,0,0,0,1,1]+[0]*13,#14
                   [1]+[0]*11+[1,0,0,0,1,0,0,0,0,0,0,0,0,1]+[0]*8,#15
                   [0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,1,0,0,0,1]+[0]*8,#16,
                   [0]*10+[1,0,0,0,0,0,1,0,1,0,0,1,1]+[0]*11,#17
                   [0]*10+[1,0,0,1,0,0,0,1,0,1,0,0,1,1]+[0]*10,#18,
                   [0]*13+[1,1,0,0,0,1,0,1,0,0,1,1]+[0]*9,#19
                   [0]*14+[1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1],#20
                   [0]*16+[1,1,0,0,0,0,1,0,0,1,1]+[0]*7,#21
                   [0]*17+[1,1,0,0,1,0,1,0,0,1,1]+[0]*6,#22
                   [0]*18+[1,1,0,0,1,0,1,0,0,1,1]+[0]*5,#23
                   [0]*19+[1,1,0,0,1,0,0,0,0,1,0,0,0,0,1],#24
                   [0]*15+[1,1,0,0,0,0,1,0,0,0,0,1]+[0]*7,#25
                   [0]*21+[1,1,0,0,1,0,1]+[0]*6,#26
                   [0]*22+[1,1,0,0,1,0,1,1,1,1,0,0],#27
                   [0]*23+[1,1,0,0,1,0,0,0,0,1,0],#28
                   [0]*27+[1]+[0]*6,#29
                   [0]*27+[1]+[0]*6,#30
                   [0]*27+[1]+[0]*6,#31
                   [0]*28+[1]+[0]*5,#32
                   [0]*20+[1,0,0,0,1]+[0]*9#33
                   ])
np.fill_diagonal(linjie, 1)


if not os.path.exists('distance_shortest.npz'):
    if os.path.exists('distance.npz'):
        c = np.load('distance.npz')
        W = c['W']
        R = c['R']
    else:
        W = np.full((34,34),np.inf)
        R = np.full((34,34),-1)
        for j in range(34):
            R[linjie[:,j] == 1,j] = j
    
        # =============================================================================
        #     W初始化
        # =============================================================================
          
        for i in range(34):
            for j in range(i+1,34,1):
                if 1 == linjie[i,j]:
                    W[i,j] = eval(input('请输入{}和{}两省省会之间距离（单位：公里）:'.format(findProvinceName(i), findProvinceName(j))))
                    W[j,i] = W[i,j]
                    
        np.savez('distance.npz', W = W, R = R)
    
    # Floyd Algorithm  
    for k in range(34):
        for i in range(34):
            for j in range(34):
                if W[i,k]+W[k,j] < W[i,j]:
                    W[i,j] = W[i,k] + W[k,j]
                    R[i,j] = R[i,k]
    np.savez('distance_shortest.npz',W = W,R = R)

else:
     c = np.load('distance_shortest.npz')
     W = c['W']
     R = c['R']
         
         
def findShortestPath(s,t,*args): 
    if len(args) == 1 and args[0] == True:
        # 查看最短路径的路由             
        index = provinces[s]
        shortest_path =[index]
        while R[index, provinces[t]] != provinces[t]:
            index = R[index, provinces[t]]
            shortest_path.append(index)
        shortest_path.append(provinces[t])
        print('{}到{}的最短路径：{}'.format(s,t,'->'.join([findProvinceName(x) for x in shortest_path])))
    return W[provinces[s],provinces[t]]
    

# print(findShortestPath('甘肃','台湾',True))
    # tihuo_province = '新疆'
    # xiehuo_province = '甘肃'
    # index = provinces[tihuo_province]
    # shortest_path =[index]
    # while R[index, provinces[xiehuo_province]] != provinces[xiehuo_province]:
    #     index = R[index, provinces[xiehuo_province]]
    #     shortest_path.append(index)
    # shortest_path.append(provinces[xiehuo_province])
    # print('{}到{}的最短距离:{} km, 路径:{}'.format(tihuo_province,xiehuo_province,\
    #                                        W[provinces[tihuo_province], provinces[xiehuo_province]],\
    #                                        '->'.join([findProvinceName(x) for x in shortest_path])))